package com.zyj.test.month1.day10;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author Yijia Zhang
 * @create 2024-05-17 08:49
 */
public class code0826 {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int len = difficulty.length;
        if (len == 0) {
            return 0;
        }
        int[][] arr = new int[len][2];
        for (int i = 0; i < len; i++) {
            arr[i] = new int[] {difficulty[i], profit[i]};
        }
        Arrays.sort(arr, (Comparator.comparingInt(i -> i[0])));
        int[] maxPre = new int[len];
        int max = arr[0][1];
        for (int i = 0; i < len; i++) {
            max = Math.max(arr[i][1], max);
            maxPre[i] = max;
        }
        //二分查找找到小于等于worker[i]的index
        int res = 0;
        for (int w : worker) {
            if (w < arr[0][0]) {
                continue;
            }
            int l = 0, r = len - 1;
            while (l < r) {
                int mid = l + (r - l + 1 >> 1);
                if (arr[mid][0] <= w) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }

            res += maxPre[l];
        }
        return res;
    }
}
